package org.xqh.study.leetcode.algorithm.studyplan;

import com.alibaba.fastjson.JSON;
import org.xqh.study.leetcode.algorithm.studyplan.Trie.TrieNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @ClassName DictTree
 * @Description 字典树
 * @Author xuqianghui
 * @Date 2021/3/6 16:48
 * @Version 1.0
 */
public class DictTree {

    public static void main(String[] args) {
        char[][] board = {{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}};
        String[] words = {"oath","pea","eat","rain"};

//        char[][] board = {{'a', 'a'}};
//        String[] words = {"aaa"};

        System.out.println(JSON.toJSONString(findWords(board, words)));
    }

    public static int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};

    /**
     * 耗时1ms
     * @param board
     * @param words
     * @return
     */
    public static List<String> findWords(char[][] board, String[] words){
        int rows = board.length;
        int cols = board[0].length;
        List<String> ans = new ArrayList<>();
        for(String w:words){
            char[] arr = w.toCharArray();
            p: for(int i = 0; i < rows; i ++){
                for(int j = 0; j < cols; j++){
                    if(board[i][j] != arr[0]){
                        continue;
                    }
                    boolean[][] used = new boolean[rows][cols];
                    used[i][j] = true;
                    if(dfs(board, i, j, 0, arr, used)){
                        ans.add(w);
                        break p;
                    }
                }
            }
        }
        return ans;
    }

    public static boolean dfs(char[][] board, int i, int j, int depth, char[] ch, boolean[][] used){

        if(depth == ch.length - 1){
            return true;
        }

        for(int k = 0; k < 4; k ++){
            int ni = directions[k][0] + i;
            int nj = directions[k][1] + j;
            if(ni < 0 || nj < 0 || ni >= board.length || nj >= board[0].length || used[ni][nj]){
                continue;
            }
            if(board[ni][nj] == ch[depth+1]){
                used[ni][nj] = true;
                boolean ret = dfs(board, ni, nj, depth + 1, ch, used);
                if(ret){
                    return true;
                }
            }
            used[ni][nj] = false;
        }

        return false;
    }

    public static List<String> findWords22(char[][] board, String[] words) {
        Trie trie = new Trie();//构建 前缀树
        List<String> result = new ArrayList<>();
        for(String word:words){
            trie.insert(word);//插入节点
        }

        int rows = board.length;
        int cols = board[0].length;
        TrieNode node = trie.root;
        boolean[][] used = new boolean[rows][cols];
        for(int i = 0; i < rows; i ++){
            for(int j = 0; j < cols; j ++){
                char ch = board[i][j];
                if(node.containsKey(ch)){//
                    Deque<String> deque = new ArrayDeque<>();
                    deque.offer(String.valueOf(ch));
                    used[i][j] = true;
                    dfs(node.get(ch), deque, board, i, j, result, used);
                    deque.pollLast();
                    used[i][j] = false;
                }
            }
        }

        return result;
    }

    public static void dfs(TrieNode node, Deque<String> deque, char[][] board, int i, int j, List<String> result, boolean[][] used){

        if(node.getEnd()){
            node.setEnd(false);//修剪调 已处理过得节点
            StringBuilder sb = new StringBuilder();
            //最终节点
            for(String c:deque){
                sb.append(c);
            }
            String sub = sb.toString();
            if(!result.contains(sub)){
                result.add(sub);
            }
        }

        for(int k = 0; k < directions.length; k ++){
            int ni = directions[k][0] + i;
            int nj = directions[k][1] + j;
            //边界判断
            if(ni < 0 || nj < 0 || ni >= board.length || nj >= board[0].length || used[ni][nj]){
                continue;
            }
            char ch = board[ni][nj];
            if(!node.containsKey(ch)){
                continue;
            }
            deque.offer(String.valueOf(ch));
            used[ni][nj] = true;
            dfs(node.get(ch), deque, board, ni, nj, result, used);
            deque.pollLast();
            used[ni][nj] = false;
        }
    }

}
